#include <vector>
#include <algorithm>
#include <queue>

using namespace std;


class Solution {
public:
    // 这方法貌似太慢了。。
    int count = 0;
    int change(int amount, vector<int>& coins) {
        sort(coins.begin(), coins.end());
        dfs(amount, coins, coins.size()-1);
        return count;
    }

    void dfs(int amount, vector<int>& coins, int upper) {
        if (amount == 0) {
            count++;
            return;
        }
        for (int i=0; i<=upper; ++i) {
            int coin = coins[i];
            if (amount-coin >= 0) {
                dfs(amount-coin, coins, i);
            }
        }
    }


    int changeBFS(int amount, vector<int>& coins) {
        int count = 0;
        sort(coins.begin(), coins.end());
        queue<tuple<int, int>> q;
        q.push({amount, coins.size()-1});
        while (!q.empty()) {
            tuple<int, int> pair = q.front(); q.pop();
            int amountCurr = get<0>(pair);
            int upper = get<1>(pair);
            if (amount == 0) {
                count++;
                continue;
            }
            for (int i=0; i<=upper; ++i) {
                int coin = coins[i];
                if (amountCurr-coin >= 0) {
                    q.push({amountCurr-coin, i});
                }
            }
        }
        return count;
    }
};
